Electronic messages are generally transmitted between remote correspondents via a communications system typically including a network of interconnected computers. Such messages are readily intercepted and viewed by others using the network. Thus, correspondents desiring privacy may encrypt or encode a message such that only the recipient can decrypt or decode the message to view the contents.
In a public key encryption system, a person wishing to receive encrypted messages (a potential recipient) is able to generate a special set of numeric values. Some of these numeric values are published by the recipient as a public key and the remaining numeric values are kept as the recipient's private key. A second person (a sender) wishing to send an encrypted message to the recipient, first obtains the recipient's public key, and then encrypts a message using this public key information. The message is then sent to the recipient. The recipient is then able to use his or her private key information to decrypt the encrypted message much more rapidly than a message eavesdropper who does not have the private key information. In all public key schemes known, there is a mathematical relationship between the private key and the public key. Finding the private key via the mathematical relationship can be made arbitrarily difficult at the expense of encryption and/or decryption performance.
A well-known encryption technique is disclosed in U.S. Pat. No. 4,405,829 to Rivest et al., which is incorporated by reference. The technique is also known as the RSA public key system. The RSA algorithm performs integer arithmetic modulo n, where n is a product of two large, randomly chosen prime numbers. A recipient generates a private exponent key using knowledge of the prime factors and a chosen public exponent. The public exponent and modulus n is published as the public key. The message sender uses the public key information to break up messages into pieces, each of which is numerically encoded in an agreed-on format to lie in the modulus range. The sender then takes each piece of the message as a numeric value and raises it to the public exponent, with the result calculated as modulo n. The result of encoding each piece is an encrypted value.
The above-described “power-mod” process is generally fast for small powers, so public exponents, tend to be relatively small compared to n. The sender then packs all the values in an agreed-on format to form the encrypted message. The recipient takes the message and breaks it up into the same sets of encrypted values modulo n. For each value, the recipient raises the encrypted message to their private exponent modulo n. This results in using the power-mod function again. Each resulting value is then unpacked to reclaim the original encrypted message.
To ensure security, n must be chosen so that factorization into its prime factors is not feasible using the fastest known algorithms. If n's factors can be found, then the private exponent can be easily calculated. Unfortunately, in terms of performance, the private exponent is generally a large number less than the modulus n, and the power-mod function is relatively slow for large n when compared with multiplication.
For a secure 1024-bit modulus n, a typical 1 GHz processor can encrypt data using the RSA algorithm with a secure public exponent of 216+1 at a rate of around 125,000 bits per second. Decryption is around 50 times slower at about 2,500 bits per second. This decryption performance may be adequate for non-real time systems, particularly if a public key is used to encrypt a secret symmetric-key and send it to the recipient first. All subsequent information then can be encrypted using the symmetric-key, which improves performance, as symmetric-key algorithms are generally much faster.
In her book, “In Code: A Mathematical Journey”, (ISBN 0-7611-2384-9) Sarah Flannery describes what she calls the “Cayley Purser” public key algorithm in Appendix A which requires finding matrices A and C in GL(2, Zn) that are not multiplicatively commutative, i.e.:AC≢CA
The algorithm then requires generating matrix B using:B=(C−1A−1C)mod n  (A1)
The algorithm further requires generating the matrix G using:G=(Ck)
Where k is a chosen integer greater than 1 or less than −1 so that matrix C cannot be trivially found from matrix G. The C matrix is the private key. {A, B, G, n} form the public key. The matrix rank is assumed to be 2. In the Postscript of Appendix A [see [6.3], pages 290–292], Flannery describes a security flaw in her algorithm because when calculating matrix B above, the matrices to the left and right of matrix A in equation (A1) are relatively inverse to each other, so that any linear multiple of C (modulo n) is also a solution to equation (A1).
In many network applications, client-server models of computer interactions over networks use context-less servers, where the server knows nothing about the client, so all context-specific information is kept on client systems. Cookies are an example of client context information, which are kept on client systems instead of web servers.
The original IP (Internet Protocol) packet transmission protocol is a session-less packet transmission protocol used widely on the Internet. Any concept of communications sessions is kept at a higher level, for example, in applications such as TCP (Transmission Control Protocol). The secure version of IP, called IPSec, is an extremely complex protocol, designed for all applications requiring use of IP. It is therefore used in a session-less manner, i.e., it is not informed when communication sessions begin and end. To minimize the slowness of public key systems, IPSec frequently uses secret (symmetric) key encryption and decryption, where the same key is used to both encrypt and decrypt a message. This in turn requires a secret key exchange, followed by keeping secret keys at both ends of the secure communications path for a period of time that is invisible at the application layer. This secret key persistence is termed a SA (Security Association). SAs are not instantiated at the application level, but must occur and be maintained by IPSec itself, while IPSec is being used in a session-less manner by applications. This makes maintenance of a security state on a multi-client system such as a web server a very complex task, requiring expiring and overlapping SAs, and increased use of processor and memory resources.
To provide context-less servers with public-key encryption, it is desirable not to keep client-specific private symmetric-keys on the server. In this case, the slow decryption rate of public keys can be a problem, even when they are used only to exchange a secret key. Further, the processing requirements for performing simultaneous encryption and decryption should be reduced, allowing for use in low-power applications, such as cell phones, or web-based radio communication systems, such as, blue-tooth and wire-less LAN.
Thus, there is a need for a public key system that can perform both encryption and decryption with relatively fewer calculations, which can result in a higher encryption/decryption throughput, and/or lower power consumption.